package graph.traversal;

import java.util.*;

/**
 * @Classname : ConnectingCitiesWithMinimumCost
 * @Description :
 * <a href="https://leetcode.cn/problems/connecting-cities-with-minimum-cost/">1135. 最低成本联通所有城市</a>
 * 加权无向图：广度优先搜索 + 权重优先搜索
 * @Author : chentianyu
 * @Date 2023/2/6 22:39
 */


public class ConnectingCitiesWithMinimumCost {
    public int minimumCost(int n, int[][] connections) {
        // 建立邻接矩阵
        List<List<int[]>> matrix = new ArrayList<>();
        for (int i = 0; i <= n; i++) matrix.add(new ArrayList<>());
        for (int[] connection : connections) {
            int u = connection[0], v = connection[1], w = connection[2];
            matrix.get(u).add(new int[]{v, w});
            matrix.get(v).add(new int[]{u, w});
        }
        // 优先遍历获取最小成本
        int minCost = 0;
        Queue<int[]> q = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));
        Set<Integer> visited = new HashSet<>();
        q.offer(new int[]{1, 0});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int to = cur[0], cost = cur[1];
            // 若目标城市已经遍历，则当前边无效
            if (visited.contains(to)) continue;
            minCost += cost;
            visited.add(to);
            for (int[] toAndCost : matrix.get(to)) {
                q.offer(toAndCost);
            }
        }
        // 已遍历节点数小于全部节点数，说明城市未完全联通
        if (visited.size() < n) return -1;
        return minCost;
    }
}
